The malarial PfA-M1 metallo-aminopeptidase is considered a putative drug target. The natural product dipeptide mimetic, bestatin, is a potent inhibitor of PfA-M1. Herein we present a new, efficient, and high-yielding protocol for the synthesis of bestatin derivatives from natural and unnatural N-Boc-d-amino acids. A diverse library of bestatin derivatives was synthesized with variants at the side chain of either the α-hydroxy-β-amino acid (P1) or the adjacent natural α-amino acid (P1'). Surprisingly, we found that extended aromatic side chains at the P1 position resulted in potent inhibition against PfA-M1. To understand these data, we determined the X-ray cocrystal structures of PfA-M1 with two derivatives having either a Tyr(OMe) 15 or Tyr(OBzl) 16 at the P1 position and observed substantial inhibitor-induced rearrangement of the primary loop within the PfA-M1 pocket that interacts with the P1 side chain. Our data provide important insights for the rational design of more potent and selective inhibitors of this enzyme that may eventually lead to new therapies for malaria.